{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cousins in Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isCousins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的堂兄弟节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在二叉树中，根节点位于深度 <code>0</code> 处，每个深度为 <code>k</code> 的节点的子节点位于深度 <code>k+1</code> 处。</p>\n",
    "\n",
    "<p>如果二叉树的两个节点深度相同，但<strong> 父节点不同</strong> ，则它们是一对<em>堂兄弟节点</em>。</p>\n",
    "\n",
    "<p>我们给出了具有唯一值的二叉树的根节点 <code>root</code> ，以及树中两个不同节点的值 <code>x</code> 和 <code>y</code> 。</p>\n",
    "\n",
    "<p>只有与值 <code>x</code> 和 <code>y</code> 对应的节点是堂兄弟节点时，才返回 <code>true</code> 。否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：<br />\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/16/q1248-01.png\" style=\"height: 160px; width: 180px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4], x = 4, y = 3\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：<br />\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/16/q1248-02.png\" style=\"height: 160px; width: 201px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,4,null,5], x = 5, y = 4\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/16/q1248-03.png\" style=\"height: 160px; width: 156px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,4], x = 2, y = 3\n",
    "<strong>输出：</strong>false</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点数介于 <code>2</code> 到 <code>100</code> 之间。</li>\n",
    "\t<li>每个节点的值都是唯一的、范围为 <code>1</code> 到 <code>100</code> 的整数。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cousins-in-binary-tree](https://leetcode.cn/problems/cousins-in-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cousins-in-binary-tree](https://leetcode.cn/problems/cousins-in-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n4\\n3', '[1,2,3,null,4,null,5]\\n5\\n4', '[1,2,3,null,4]\\n2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        que = [[root, None]]\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            temp = []\n",
    "            for i in range(size):\n",
    "                node_parent = que[0]\n",
    "                del que[0]\n",
    "                if node_parent[0].val in (x, y):\n",
    "                    if not temp:\n",
    "                        temp.append(node_parent)\n",
    "                    else:\n",
    "                        return temp[0][1] != node_parent[1]\n",
    "                if node_parent[0].left:\n",
    "                    que.append(\n",
    "                        [node_parent[0].left, node_parent[0]]\n",
    "                    )\n",
    "                if node_parent[0].right:\n",
    "                    que.append(\n",
    "                        [node_parent[0].right, node_parent[0]]\n",
    "                    )\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:\n",
    "        # x 的信息\n",
    "        x_parent, x_depth, x_found = None, None, False\n",
    "        # y 的信息\n",
    "        y_parent, y_depth, y_found = None, None, False\n",
    "        \n",
    "        def dfs(node: TreeNode, depth: int, parent: TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found\n",
    "            \n",
    "            if node.val == x:\n",
    "                x_parent, x_depth, x_found = parent, depth, True\n",
    "            elif node.val == y:\n",
    "                y_parent, y_depth, y_found = parent, depth, True\n",
    "\n",
    "            # 如果两个节点都找到了，就可以提前退出遍历\n",
    "            # 即使不提前退出，对最坏情况下的时间复杂度也不会有影响\n",
    "            if x_found and y_found:\n",
    "                return\n",
    "\n",
    "            dfs(node.left, depth + 1, node)\n",
    "\n",
    "            if x_found and y_found:\n",
    "                return\n",
    "\n",
    "            dfs(node.right, depth + 1, node)\n",
    "\n",
    "        dfs(root, 0, None)\n",
    "        return x_depth == y_depth and x_parent != y_parent\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        ad, af, bd, bf = None, None, None, None\n",
    "        queue = deque()\n",
    "        queue.append((root, None))\n",
    "        depth = 0\n",
    "        while queue:\n",
    "            ln = len(queue)\n",
    "            depth += 1\n",
    "            for _ in range(ln):\n",
    "                node = queue.popleft()\n",
    "                if node[0].val == x:\n",
    "                    ad = depth\n",
    "                    af = node[1]\n",
    "                if node[0].val == y:\n",
    "                    bd = depth\n",
    "                    bf = node[1]\n",
    "                if node[0].left:\n",
    "                    queue.append((node[0].left, node[0]))\n",
    "                if node[0].right:\n",
    "                    queue.append((node[0].right, node[0]))\n",
    "        return ad == bd and af != bf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        self.x_parent =None\n",
    "        self.y_parent =None\n",
    "        self.x_depth =None\n",
    "        self.y_depth =None\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.traverse(root,0)\n",
    "\n",
    "        if self.x_depth==self.y_depth and self.x_parent != self.y_parent:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    \n",
    "    def traverse(self,root,depth):\n",
    "        if not root:\n",
    "            return \n",
    "        depth += 1\n",
    "\n",
    "        if root.left :\n",
    "            if self.x == root.left.val:\n",
    "                self.x_parent = root\n",
    "                self.x_depth = depth +1\n",
    "            elif self.y == root.left.val:\n",
    "                self.y_parent = root\n",
    "                self.y_depth = depth +1\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "        if root.right:\n",
    "            if self.x == root.right.val:\n",
    "                self.x_parent = root\n",
    "                self.x_depth = depth +1\n",
    "            elif self.y == root.right.val:\n",
    "                self.y_parent = root\n",
    "                self.y_depth = depth +1\n",
    "            else:\n",
    "                pass\n",
    "        self.traverse(root.left,depth)\n",
    "        self.traverse(root.right,depth)\n",
    "        depth -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None, parent=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        from collections import deque\n",
    "        dq = deque()\n",
    "        dq.appendleft((root, None))\n",
    "        level_parents = []\n",
    "        while dq:\n",
    "            for i in range(len(dq)):\n",
    "                cur_node, parent = dq.popleft()\n",
    "                if cur_node.val == x or cur_node.val == y:\n",
    "                    level_parents.append(parent)\n",
    "                if cur_node.left:\n",
    "                    dq.append((cur_node.left, cur_node))\n",
    "                if cur_node.right:\n",
    "                    dq.append((cur_node.right, cur_node))\n",
    "            if not level_parents:\n",
    "                continue\n",
    "            if len(level_parents) == 1:\n",
    "                return False\n",
    "            if len(level_parents) == 2:\n",
    "                return level_parents[0] != level_parents[1]\n",
    "        # return False\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "    def get_parent(self, root):\n",
    "        if not root.left and not root.right:\n",
    "            return\n",
    "        while root.left:\n",
    "            root.left.parent = root\n",
    "            root = root.left\n",
    "        while root.right:\n",
    "            root.right.parent = root\n",
    "            root = root.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_depth, x_parent, y_depth, y_parent, = None, None, None, None\n",
    "\n",
    "        def dfs(root, parent, x, y, depth):\n",
    "            nonlocal x_depth, x_parent, y_depth, y_parent\n",
    "            if root is None:\n",
    "                return\n",
    "\n",
    "            if root.val == x:\n",
    "               x_parent = parent\n",
    "               x_depth = depth\n",
    "            if root.val == y:\n",
    "                y_depth = depth\n",
    "                y_parent = parent\n",
    "    \n",
    "            dfs(root.left, root, x, y, depth + 1)\n",
    "            dfs(root.right, root, x, y, depth + 1)\n",
    "\n",
    "        dfs(root, None, x, y, 0)\n",
    "        return x_depth == y_depth and x_parent != y_parent\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_d,y_d,x_p,y_p = None,None,None,None\n",
    "        def dfs(root,parent,x,y,depth):\n",
    "            nonlocal x_d, y_d, x_p, y_p\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val == x:\n",
    "                x_d = depth\n",
    "                x_p = parent\n",
    "            if root.val == y:\n",
    "                y_d = depth\n",
    "                y_p = parent\n",
    "            dfs(root.left,root,x,y,depth+1)\n",
    "            dfs(root.right,root,x,y,depth+1)\n",
    "        dfs(root,None,x,y,0)\n",
    "        return x_d == y_d and x_p != y_p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        res_x=[]\n",
    "        res_y=[]\n",
    "        def dfs(node,parent,deep):\n",
    "            nonlocal res_x,res_y\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.val==x:\n",
    "                res_x=[parent,deep]\n",
    "            elif node.val==y:\n",
    "                res_y=[parent,deep]\n",
    "            dfs(node.left,node,deep+1)\n",
    "            dfs(node.right,node,deep+1)\n",
    "        dfs(root,root,0)\n",
    "        return res_x[0]!=res_y[0] and res_x[1]==res_y[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None, parent=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        from collections import deque\n",
    "        dq = deque()\n",
    "        dq.appendleft((root, None))\n",
    "        level_parents = []\n",
    "        while dq:\n",
    "            # cur_level = []\n",
    "            for i in range(len(dq)):\n",
    "                cur_node, parent = dq.popleft()\n",
    "                if cur_node.val == x or cur_node.val == y:\n",
    "                    level_parents.append(parent)\n",
    "                if cur_node.left:\n",
    "                    dq.append((cur_node.left, cur_node))\n",
    "                if cur_node.right:\n",
    "                    dq.append((cur_node.right, cur_node))\n",
    "            if not level_parents:\n",
    "                continue\n",
    "            if len(level_parents) == 1:\n",
    "                return False\n",
    "            if len(level_parents) == 2:\n",
    "                return level_parents[0] != level_parents[1]\n",
    "        return False\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "    def get_parent(self, root):\n",
    "        if not root.left and not root.right:\n",
    "            return\n",
    "        while root.left:\n",
    "            root.left.parent = root\n",
    "            root = root.left\n",
    "        while root.right:\n",
    "            root.right.parent = root\n",
    "            root = root.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        self.x_level = None\n",
    "        self.y_level = None\n",
    "        self.x_p = None\n",
    "        self.y_p = None\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        def dfs(parent, node, level):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.val == self.x:\n",
    "                self.x_p = parent\n",
    "                self.x_level = level\n",
    "            if node.val == self.y:\n",
    "                self.y_p = parent\n",
    "                self.y_level = level\n",
    "            dfs(node, node.left, level + 1)\n",
    "            dfs(node, node.right, level + 1)\n",
    "        dfs(None, root, 0)\n",
    "        return self.x_level == self.y_level and self.x_p != self.y_p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        parent={root.val:0} \n",
    "        level={root.val:0}    \n",
    "        depth=0\n",
    "        def ds(root,parent,depth,x,y):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val==x:\n",
    "                level[x]=depth+1\n",
    "            if root.val==y:\n",
    "                level[y]=depth+1\n",
    "            if root.left:                \n",
    "                parent[root.left.val]=root.val\n",
    "                ds(root.left,parent,depth+1,x,y)                \n",
    "            if root.right:\n",
    "                parent[root.right.val]=root.val\n",
    "                ds(root.right,parent,depth+1,x,y)                \n",
    "\n",
    "        ds(root,parent,depth,x,y)\n",
    "\n",
    "        #print('parent:',parent)\n",
    "        #print('level:',level)\n",
    "   \n",
    "        if level[x]==level[y] and parent[x]!=parent[y]:\n",
    "            return True\n",
    "        else:\n",
    "            return False      \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        queue = deque()\n",
    "        queue.append([root])\n",
    "        while queue:\n",
    "            lst = []\n",
    "            ans_lst = []\n",
    "            node_lst = queue.popleft()\n",
    "            for node in node_lst:\n",
    "                ans_lst.append(node)\n",
    "                if node.left:\n",
    "                    n = node.left\n",
    "                    n.father = node\n",
    "                    lst.append(n)\n",
    "                if node.right:\n",
    "                    n = node.right\n",
    "                    n.father = node\n",
    "                    lst.append(n)\n",
    "            if lst:\n",
    "                queue.append(lst)\n",
    "                \n",
    "            a, b = None, None\n",
    "            for node in ans_lst:\n",
    "                if node.val == x:\n",
    "                    a = node\n",
    "                if node.val == y:\n",
    "                    b = node\n",
    "            if (a and b) and a.father != b.father:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        if not root:    return None\n",
    "        deq = collections.deque()\n",
    "        deq.append(root)\n",
    "        while deq:\n",
    "            l = len(deq)\n",
    "            curr_level = []\n",
    "            for i in range(l):\n",
    "                temp = deq.popleft()\n",
    "                if temp.left and temp.right and \\\n",
    "                 ((temp.left.val == x and temp.right.val == y) or\\\n",
    "                 (temp.left.val == y and temp.right.val == x)):\n",
    "                 return False\n",
    "                if temp.left:   deq.append(temp.left)\n",
    "                if temp.right:  deq.append(temp.right)\n",
    "                curr_level.append(temp.val)\n",
    "            if x in curr_level:\n",
    "                if y in curr_level: return True\n",
    "                else:   return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        q = [root]\n",
    "        res = []\n",
    "        pre = root\n",
    "        while q:\n",
    "            res.clear()\n",
    "            for a in range(len(q)):\n",
    "                node = q.pop(0)\n",
    "                if node.left:\n",
    "                    if node.left.val == x or node.left.val == y:\n",
    "                        res.append((node.left.val, node.val))\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    if node.right.val == x or node.right.val == y:\n",
    "                        res.append((node.right.val, node.val))\n",
    "                    q.append(node.right)\n",
    "            if len(res) == 2 and res[0][1] != res[1][1]:\n",
    "                print(res)\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_parent,x_depth,x_found=None,None,False\n",
    "        y_parent,y_depth,y_found=None,None,False\n",
    "\n",
    "        def dfs(node:TreeNode,depth:int,parent:TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found\n",
    "\n",
    "            if node.val==x:\n",
    "               x_parent,x_depth,x_found=parent,depth,True\n",
    "            if node.val==y:\n",
    "               y_parent,y_depth,y_found=parent,depth,True\n",
    "            \n",
    "            dfs(node.left,depth+1,node)\n",
    "\n",
    "            dfs(node.right,depth+1,node)\n",
    "\n",
    "        dfs(root,0,None)\n",
    "        return x_depth == y_depth and x_parent != y_parent\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        \n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            cousins = False\n",
    "            siblings = False\n",
    "\n",
    "            for _ in range(size):\n",
    "                curr = q.popleft()\n",
    "\n",
    "                if not curr:\n",
    "                    siblings = False\n",
    "\n",
    "                else:\n",
    "                    if curr.val == x or curr.val == y:\n",
    "                        if not cousins:\n",
    "                            siblings = True\n",
    "                            cousins = True\n",
    "                        else:\n",
    "                            return not siblings\n",
    "                \n",
    "                \n",
    "                    if curr.left:\n",
    "                        q.append(curr.left)\n",
    "                    if curr.right:\n",
    "                        q.append(curr.right)\n",
    "                    \n",
    "                    q.append(None)\n",
    "            \n",
    "            if cousins:\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_parent, x_depth, y_parent, y_depth = None, None, None, None\n",
    "        queue = [(root, None)]\n",
    "\n",
    "        level = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            level += 1\n",
    "            for i in range(size):\n",
    "                node, parent = queue.pop(0)\n",
    "                if node.val == x:\n",
    "                    x_parent = parent\n",
    "                    x_depth = level\n",
    "                if node.val == y:\n",
    "                    y_parent = parent\n",
    "                    y_depth = level\n",
    "                if node.left:\n",
    "                    queue.append((node.left, node))\n",
    "                if node.right:\n",
    "                    queue. append((node.right, node))\n",
    "        return x_depth == y_depth and x_parent != y_parent\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        memo = [root]\n",
    "        while (len(memo)):\n",
    "            count = len(memo)\n",
    "            temp = []\n",
    "            for i in range(count):\n",
    "                node = memo.pop(0)\n",
    "                if node:\n",
    "                    memo.append(node.left)\n",
    "                    memo.append(node.right)\n",
    "                    temp.append(node.val)\n",
    "                else:\n",
    "                    temp.append(None)\n",
    "            flag = 0\n",
    "            for i in range(0, len(temp) - 1, 2):\n",
    "                if (temp[i] == x or temp[i+1] == x) and (temp[i] == y or temp[i+1] == y):\n",
    "                    return False\n",
    "                if temp[i] == x or temp[i+1] == x:\n",
    "                    flag += 1\n",
    "                if temp[i] == y or temp[i+1] == y:\n",
    "                    flag += 1\n",
    "            if flag == 1:\n",
    "                return False\n",
    "            if flag == 2:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        # x 的信息\n",
    "        x_parent, x_depth, x_found = None, None, False\n",
    "        # y 的信息\n",
    "        y_parent, y_depth, y_found = None, None, False\n",
    "        \n",
    "        def dfs(node: TreeNode, depth: int, parent: TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found\n",
    "            \n",
    "            if node.val == x:\n",
    "                x_parent, x_depth, x_found = parent, depth, True\n",
    "            elif node.val == y:\n",
    "                y_parent, y_depth, y_found = parent, depth, True\n",
    "\n",
    "            # 如果两个节点都找到了，就可以提前退出遍历\n",
    "            # 即使不提前退出，对最坏情况下的时间复杂度也不会有影响\n",
    "            if x_found and y_found:\n",
    "                return\n",
    "\n",
    "            dfs(node.left, depth + 1, node)\n",
    "            dfs(node.right, depth + 1, node)\n",
    "\n",
    "        dfs(root, 0, None)\n",
    "        return x_depth == y_depth and x_parent != y_parent\n",
    "        \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=993 lang=python3\n",
    "#\n",
    "# [993] 二叉树的堂兄弟节点\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_father, x_depth, x_find = None, None, False\n",
    "        y_father, y_depth, y_find = None, None, False\n",
    "        def dfs(root, father=None, depth=0):\n",
    "            nonlocal x,x_father,x_depth,x_find\n",
    "            nonlocal y,y_father,y_depth,y_find\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.val==x:\n",
    "                x_father = father\n",
    "                x_find = True\n",
    "                x_depth = depth\n",
    "            elif root.val==y:\n",
    "                y_father = father\n",
    "                y_find = True\n",
    "                y_depth = depth\n",
    "            father = root.val\n",
    "            depth += 1\n",
    "            dfs(root.left, father, depth)\n",
    "            dfs(root.right, father, depth)\n",
    "        dfs(root)\n",
    "        if (x_find and y_find) and (x_depth==y_depth) and (x_father!=y_father):\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        result_x=[]\n",
    "        result_y=[]\n",
    "        def dsf(node,father,deep):\n",
    "            nonlocal result_x\n",
    "            nonlocal result_y\n",
    "            if not node:\n",
    "                return \n",
    "            if node.val==x:\n",
    "                result_x=[father,deep]\n",
    "                \n",
    "            elif  node.val==y:\n",
    "                result_y=[father,deep]\n",
    "               \n",
    "            dsf(node.left,node,deep+1)\n",
    "            dsf(node.right,node,deep+1)\n",
    "        dsf(root,root,0)\n",
    "        if result_x[0]!=result_y[0] and result_x[1]==result_y[1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        def isXorY(node, x, y):\n",
    "            return node != None and (node.val == x or node.val == y)\n",
    "\n",
    "        q = [root]\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            cnt = 0\n",
    "            for _ in range(sz):\n",
    "                node = q.pop(0)\n",
    "                \n",
    "                if isXorY(node.left, x, y) and isXorY(node.right, x, y):\n",
    "                    return False\n",
    "                \n",
    "                if isXorY(node, x, y):\n",
    "                    cnt += 1\n",
    "                \n",
    "                if cnt == 2:\n",
    "                    return True\n",
    "                \n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                \n",
    "        \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        self.x_level = None\n",
    "        self.y_level = None\n",
    "        self.x_p = None\n",
    "        self.y_p = None\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        def dfs(parent, node, level):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.val == self.x:\n",
    "                self.x_p = parent\n",
    "                self.x_level = level\n",
    "                return\n",
    "            if node.val == self.y:\n",
    "                self.y_p = parent\n",
    "                self.y_level = level\n",
    "                return\n",
    "            if self.x_level is not None:\n",
    "                if level >= self.x_level:\n",
    "                    return\n",
    "            dfs(node, node.left, level + 1)\n",
    "            dfs(node, node.right, level + 1)\n",
    "        dfs(None, root, 0)\n",
    "        return self.x_level == self.y_level and self.x_p != self.y_p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        def bfs():\n",
    "            queue = [root]\n",
    "            judge = 1  # 判断x,y是否出自同一个父亲\n",
    "            while queue:\n",
    "                tmp = []\n",
    "                for i in range(len(queue)):\n",
    "                    node = queue.pop(0)\n",
    "                    tmp.append(node.val)\n",
    "                    l,r = node.left,node.right\n",
    "                    if l and r and ((l.val==x and r.val==y) or (l.val==y and r.val==x)):\n",
    "                        judge = 0\n",
    "                    if l:\n",
    "                        queue.append(l)\n",
    "                    if r:\n",
    "                        queue.append(r)\n",
    "                    if x in tmp and y in tmp and judge==1:\n",
    "                        self.res = True\n",
    "        self.res = False\n",
    "        bfs()\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        father = {root.val:None}\n",
    "        d = {}\n",
    "        q = [(root, 0)]\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                node, depth = q.pop(0)\n",
    "                d[node.val] = depth\n",
    "                if node.left:\n",
    "                    father[node.left.val] = node.val\n",
    "                    q.append((node.left, depth + 1))\n",
    "                if node.right:\n",
    "                    father[node.right.val] = node.val\n",
    "                    q.append((node.right, depth + 1))\n",
    "        return father[x] != father[y] and d[x] == d[y]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        q = deque([(root, 0)])\n",
    "        dx, dy = None, None\n",
    "        while q:\n",
    "            node, depth = q.popleft()\n",
    "            if node.val == x:\n",
    "                dx = depth\n",
    "            elif node.val == y:\n",
    "                dy = depth\n",
    "            if node.left:\n",
    "                q.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                q.append((node.right, depth + 1))\n",
    "            if node.left and node.right and set([x, y]) == set([node.left.val, node.right.val]):\n",
    "                return False\n",
    "        return dx == dy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    " \n",
    "class Solution:\n",
    "    def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool':\n",
    "        que = [(0,root)]\n",
    "        while que:\n",
    "            tempList = []\n",
    "            for i in range(len(que)):\n",
    "                node_ = que.pop(0)\n",
    "                node = node_[1]\n",
    "                tmp = node_[0]\n",
    "                if node.val == x or node.val == y:\n",
    "                    tempList.append((tmp,node.val))\n",
    "                if node.left:\n",
    "                    que.append((node.val,node.left))\n",
    "                if node.right:\n",
    "                    que.append((node.val,node.right))\n",
    "            if len(tempList) == 2 and tempList[0][0] != tempList[1][0]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        father = {root.val:None}\n",
    "        d = {}\n",
    "        q = [(root, 0)]\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                node, depth = q.pop(0)\n",
    "                d[node.val] = depth\n",
    "                if node.left:\n",
    "                    father[node.left.val] = node.val\n",
    "                    q.append((node.left, depth + 1))\n",
    "                if node.right:\n",
    "                    father[node.right.val] = node.val\n",
    "                    q.append((node.right, depth + 1))\n",
    "        return father[x] != father[y] and d[x] == d[y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_d,y_d,x_p,y_p = None,None,None,None\n",
    "        def dfs(root,parent,x,y,depth):\n",
    "            nonlocal x_d,y_d,x_p,y_p\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val == x:\n",
    "                x_d = depth\n",
    "                x_p = parent\n",
    "            if root.val == y:\n",
    "                y_d = depth\n",
    "                y_p = parent\n",
    "            dfs(root.left,root,x,y,depth+1)\n",
    "            dfs(root.right,root,x,y,depth+1)\n",
    "        dfs(root,None,x,y,0)\n",
    "        return x_d == y_d and x_p != y_p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        def getParentAndDepth(parent, node, value, depth):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.val == value:\n",
    "                return parent, depth\n",
    "            else:\n",
    "                return getParentAndDepth(node, node.left, value, depth + 1) or \\\n",
    "                    getParentAndDepth(node, node.right, value, depth + 1)\n",
    "        \n",
    "        parent_x, depth_x = getParentAndDepth(None, root, x, 0)\n",
    "        parent_y, depth_y = getParentAndDepth(None, root, y, 0)\n",
    "        if depth_x == depth_y and parent_x != parent_y:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        nodes=[root]\n",
    "        \n",
    "        while len(nodes)!=0:\n",
    "            news=[]\n",
    "            now=[]\n",
    "            dic={}\n",
    "            for i in nodes:\n",
    "                now.append(i.val)\n",
    "                if i.left:\n",
    "                    news.append(i.left)\n",
    "                if i.right:\n",
    "                    news.append(i.right)\n",
    "                if i.left and i.right:\n",
    "                    dic[i.left.val]=i.right.val\n",
    "            if dic.get(x,-1)==y or dic.get(y,-1)==x:\n",
    "                return False\n",
    "            if x in now and y in now:\n",
    "                \n",
    "                return True\n",
    "            if x in now or y in now:\n",
    "                return False\n",
    "            nodes=news\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_parent, x_depth, x_found = None, None, False\n",
    "\n",
    "        y_parent, y_depth, y_found = None, None, False\n",
    "\n",
    "        def dfs(node, depth, parent):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found\n",
    "            if node.val == x:\n",
    "                x_parent, x_depth, x_found = parent, depth, True\n",
    "            elif node.val == y:\n",
    "                y_parent, y_depth, y_found = parent, depth, True\n",
    "            if x_found and y_found:\n",
    "                return \n",
    "            dfs(node.left, depth + 1, node)\n",
    "\n",
    "            if x_found and y_found:\n",
    "                return \n",
    "            dfs(node.right, depth + 1, node)\n",
    "\n",
    "        dfs(root, 0 ,None)\n",
    "\n",
    "        return x_depth == y_depth and x_parent != y_parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        res = []\n",
    "        def digui(root, depth):\n",
    "            if len(res) == 2:\n",
    "                return\n",
    "            elif root == None:\n",
    "                return\n",
    "            else:\n",
    "                temp = []\n",
    "                if root.left != None:\n",
    "                    if root.left.val == x or root.left.val == y:\n",
    "                        temp.append(root.left.val)\n",
    "                if root.right != None:\n",
    "                    if root.right.val == x or root.right.val == y:\n",
    "                        temp.append(root.right.val)\n",
    "                if temp != []:\n",
    "                    temp.append(depth + 1)\n",
    "                    res.append(temp)\n",
    "                digui(root.left, depth + 1)\n",
    "                digui(root.right, depth + 1)\n",
    "        \n",
    "        digui(root, 0)\n",
    "        if len(res) == 2 and res[0][1] == res[1][1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        kx = ky = 0\n",
    "        px = py = None\n",
    "        def dfs(node=root, k=0, parent=None):\n",
    "            if node.val == x:\n",
    "                nonlocal kx, px\n",
    "                kx = k\n",
    "                px = parent\n",
    "            elif node.val == y:\n",
    "                nonlocal ky, py\n",
    "                ky = k\n",
    "                py = parent\n",
    "            if node.left:\n",
    "                dfs(node.left, k+1, node)\n",
    "            if node.right:\n",
    "                dfs(node.right, k+1, node)\n",
    "        \n",
    "        dfs()\n",
    "        return kx == ky and px is not py\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root, fa, depth, t):\n",
    "        if root is None:\n",
    "            return [-1, -1]\n",
    "        if root.val == t:\n",
    "            return [fa.val if fa else -1, depth]\n",
    "        l = self.dfs(root.left, root, depth + 1, t)\n",
    "        if l[0] != -1:\n",
    "            return l\n",
    "        return self.dfs(root.right, root, depth + 1, t)\n",
    "\n",
    "    def isCousins(self, root, x, y):\n",
    "        xi = self.dfs(root, None, 0, x)\n",
    "        yi = self.dfs(root, None, 0, y)\n",
    "        return xi[1] == yi[1] and xi[0] != yi[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:\n",
    "        x_depth, x_parent, y_depth, y_parent = None, None, None, None\n",
    "\n",
    "        # 标准dfs模板, 只是在中间加了一些判断逻辑\n",
    "        def dfs(root, parent, x, y, depth):\n",
    "            nonlocal x_depth, x_parent, y_depth, y_parent\n",
    "            if root is None:\n",
    "                return \n",
    "            \n",
    "            # 判断 x, y 是否等于当前节点的值, 是的话更新 x 或者 y 的深度和parent\n",
    "            if root.val == x:\n",
    "                x_depth = depth \n",
    "                x_parent = parent \n",
    "            if root.val == y:\n",
    "                y_depth = depth\n",
    "                y_parent = parent\n",
    "\n",
    "            dfs(root.left, root, x, y, depth+1)\n",
    "            dfs(root.right, root, x, y, depth+1)\n",
    "\n",
    "        dfs(root, None, x, y, 0)\n",
    "        # 最后保证 x, y的深度一样, 但是parent节点不一样, 这样才是堂兄弟\n",
    "        return x_depth == y_depth and x_parent != y_parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_parent, x_depth, x_found = None, None, False\n",
    "        y_parent, y_depth, y_found = None, None, False\n",
    "\n",
    "        def dfs(node, depth, parent):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            nonlocal x_parent, x_depth, x_found, y_parent, y_depth, y_found\n",
    "\n",
    "            if node.val == x:\n",
    "                x_parent, x_depth, x_found = parent, depth, True\n",
    "            elif node.val == y:\n",
    "                y_parent, y_depth, y_found = parent, depth, True\n",
    "\n",
    "            if x_found and y_found:\n",
    "                return\n",
    "            \n",
    "            dfs(node.left, depth+1, node)\n",
    "\n",
    "            if x_found and y_found:\n",
    "                return\n",
    "            \n",
    "            dfs(node.right, depth + 1, node)\n",
    "        \n",
    "        x_found = False\n",
    "        y_found = False\n",
    "        dfs(root, 0, None)\n",
    "        return x_depth == y_depth and x_parent != y_parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def get_parent_and_length(self, root: TreeNode, x: int):\n",
    "        queue = [(root, None, 0)]\n",
    "        while queue:\n",
    "            node, parent, length = queue.pop(0)\n",
    "            if node.val == x:\n",
    "                return node, parent, length\n",
    "            else:\n",
    "                if node.left:\n",
    "                    queue.append((node.left, node, length+1))\n",
    "                if node.right:\n",
    "                    queue.append((node.right, node, length+1))\n",
    "        return None, None, None\n",
    "\n",
    "    def get_parent_and_length_r(self, node: TreeNode, parent: TreeNode, length: int, x: int):\n",
    "        if node.val == x:\n",
    "            return node, parent, length\n",
    "        if node.left:\n",
    "            result = self.get_parent_and_length_r(node.left, node, length+1, x)\n",
    "            if result:\n",
    "                return result\n",
    "        if node.right:\n",
    "            result = self.get_parent_and_length_r(node.right, node, length+1, x)\n",
    "            if result:\n",
    "                return result\n",
    "        return None\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        _, x_parent, x_length = self.get_parent_and_length_r(root, None, 0, x)\n",
    "        _, y_parent, y_length = self.get_parent_and_length_r(root, None, 0, y)\n",
    "        return x_parent is not None and y_parent is not None and x_parent.val!=y_parent.val and x_length == y_length\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        cnt=collections.defaultdict()\n",
    "        stack=collections.deque()\n",
    "        stack.append([root,0,-1])\n",
    "\n",
    "        while stack:\n",
    "            cur,d,f =stack.popleft()\n",
    "            if cur.val in cnt:\n",
    "                continue\n",
    "            cnt[cur.val]=[d,f]\n",
    "            if cur.left:\n",
    "                stack.append([cur.left,d+1,cur])\n",
    "            if cur.right:\n",
    "                stack.append([cur.right,d+1,cur])\n",
    "        #print(cnt)\n",
    "        return cnt[x][0]==cnt[y][0] and cnt[x][1]!=cnt[y][1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        self.same = False\n",
    "        self.x_h = -1\n",
    "        self.y_h = -1\n",
    "        \n",
    "        def dfs(node, temp):\n",
    "            if node is None:\n",
    "                return \n",
    "            if node.left and node.right:\n",
    "                if (node.left.val==x and node.right.val==y) or \\\n",
    "                    (node.left.val==y and node.right.val==x):\n",
    "                    self.same = True\n",
    "            if node.val == x:\n",
    "                self.x_h = temp\n",
    "            if node.val == y:\n",
    "                self.y_h = temp\n",
    "            dfs(node.left, temp+1)\n",
    "            dfs(node.right, temp+1)\n",
    "            pass\n",
    "\n",
    "        dfs(root, 0)\n",
    "        if self.x_h == self.y_h and self.same==False:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_parent = None\n",
    "        y_parent = None\n",
    "        x_depth = None\n",
    "        y_depth = None\n",
    "\n",
    "        level = 0\n",
    "        stack = [(root, None)]\n",
    "        while stack:\n",
    "            lenstack = len(stack)\n",
    "            level += 1\n",
    "            for i in range(lenstack):\n",
    "                cur, parent = stack.pop(0)\n",
    "                if cur.val == x:\n",
    "                    x_depth = level\n",
    "                    x_parent = parent\n",
    "                if cur.val == y:\n",
    "                    y_depth = level\n",
    "                    y_parent = parent\n",
    "                if cur.left:\n",
    "                    stack.append((cur.left, cur))\n",
    "                if cur.right:\n",
    "                    stack.append((cur.right, cur))\n",
    "        return x_depth == y_depth and x_parent != y_parent\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        xf = yf = False\n",
    "        xp = yp = None\n",
    "        xd = yd = 0\n",
    "\n",
    "        def dfs(node, parent, dep):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            nonlocal xf, yf, xp, yp, xd, yd\n",
    "            if node.val == x:\n",
    "                xf = True\n",
    "                xp = parent\n",
    "                xd = dep\n",
    "\n",
    "            if node.val == y:\n",
    "                yf = True\n",
    "                yp = parent\n",
    "                yd = dep\n",
    "\n",
    "            if xf and yf:\n",
    "                return\n",
    "            dfs(node.left, node, dep + 1)\n",
    "            dfs(node.right, node, dep + 1)\n",
    "\n",
    "        dfs(root, root, 0)\n",
    "        return xd == yd and xp != yp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_depth,x_parent,y_depth,y_parent=None,None,None,None\n",
    "        def find(root,parent,x,y,depth):\n",
    "            nonlocal x_depth,x_parent,y_depth,y_parent\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.val==x:\n",
    "                x_depth=depth\n",
    "                x_parent=parent\n",
    "            if root.val==y:\n",
    "                y_depth=depth\n",
    "                y_parent=parent\n",
    "            find(root.left,root,x,y,depth+1)\n",
    "            find(root.right,root,x,y,depth+1)\n",
    "        find(root,None,x,y,0)\n",
    "        return x_depth==y_depth and x_parent!=y_parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        q = deque()\n",
    "        q.append((root,0))\n",
    "        flag = {}\n",
    "        if root.val == x or root.val == y:\n",
    "            return False\n",
    "        while q:\n",
    "            node, depth = q.popleft()\n",
    "            if node.left:\n",
    "                q.append((node.left, depth + 1))\n",
    "                if node.left.val == x or node.left.val == y:\n",
    "                    flag[node.val] = (1, depth + 1)\n",
    "            if node.right:\n",
    "                q.append((node.right, depth + 1))\n",
    "                if node.right.val == x or node.right.val == y:\n",
    "                    if node.val not in flag:\n",
    "                        flag[node.val] = (1, depth + 1)\n",
    "                    else:\n",
    "                        return False\n",
    "        a = []\n",
    "        for key in flag:\n",
    "            m = flag[key]\n",
    "            if m[0] == 1:\n",
    "                a.append(m[1])\n",
    "        # print(a)\n",
    "        return a[0] == a[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        self.ans = False \n",
    "        def dfs(root, depth, x, y):\n",
    "            if not root: return None \n",
    "            if root.val == x or root.val == y: return depth \n",
    "            l = dfs(root.left, depth + 1, x, y)\n",
    "            r = dfs(root.right, depth + 1, x, y)\n",
    "            if l and r and l == r and (root.left.val not in [x, y] or root.right.val not in [x,y]):\n",
    "                self.ans = True \n",
    "            if l and r:\n",
    "                return None \n",
    "            if l: return l \n",
    "            if r: return r \n",
    "        dfs(root, 0, x, y)\n",
    "        return self.ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        # 深度相同（同一层）但父节点不同的两个结点被称为堂兄弟结点\n",
    "        queue = deque([root, ])  # 初始化队列为根节点\n",
    "        flag = False\n",
    "        while queue:\n",
    "            size = len(queue)  # size是当前层结点个数\n",
    "            level = []  # 临时数组，记录当前层结点值\n",
    "\n",
    "            for _ in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if not cur:  # 在队列添加cur左右子节点的时候，可能会遇到cur左右子节点为空的情况，此时直接跳出就好了\n",
    "                    level.append(None)\n",
    "                    continue\n",
    "                level.append(cur.val)\n",
    "                queue.append(cur.left)\n",
    "                queue.append(cur.right)\n",
    "            \n",
    "            if x in level and y in level:\n",
    "                index_diff = abs(level.index(x) - level.index(y))\n",
    "                two_dimen = [level[i:i+2] for i in range(0, len(level), 2)]\n",
    "                a = [min(x,y), max(x, y)]\n",
    "                b = a[::-1]\n",
    "                if index_diff >= 2 or index_diff==1 and len(level) > 2 and a not in two_dimen and b not in two_dimen:\n",
    "                    flag = True\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        xDepth, xParent, xFound = 0, None, False\n",
    "        yDepth, yParent, yFound = 0, None, False\n",
    "        def update(node: TreeNode, parent: TreeNode, depth: int) -> None:\n",
    "            if node.val == x:\n",
    "                nonlocal xDepth, xParent, xFound\n",
    "                xDepth, xParent, xFound = depth, parent, True\n",
    "            elif node.val == y:\n",
    "                nonlocal yDepth, yParent, yFound\n",
    "                yDepth, yParent, yFound = depth, parent, True\n",
    "        nodeQueue, depthQueue = [root], [0]\n",
    "        update(root, None, 0)\n",
    "        while nodeQueue:\n",
    "            node, depth = nodeQueue.pop(0), depthQueue.pop(0)\n",
    "            if node.left:\n",
    "                nodeQueue.append(node.left)\n",
    "                depthQueue.append(depth+1)\n",
    "                update(node.left, node, depth+1)\n",
    "            if node.right:\n",
    "                nodeQueue.append(node.right)\n",
    "                depthQueue.append(depth+1)\n",
    "                update(node.right, node, depth+1)\n",
    "            if xFound and yFound:\n",
    "                break\n",
    "        return xDepth==yDepth and xParent!=yParent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        res = []\n",
    "        q = deque()\n",
    "        q.append((root, None, 1, 0))\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for i in range(l):\n",
    "                temp = q.popleft()\n",
    "                if temp[2] == x or temp[2] == y:\n",
    "                    res.append(temp)\n",
    "                if temp[0].left:\n",
    "                    q.append((temp[0].left, temp[2], temp[0].left.val, temp[3] + 1))\n",
    "                if temp[0].right:\n",
    "                    q.append((temp[0].right, temp[2], temp[0].right.val, temp[3] + 1))\n",
    "        if len(res) == 2 and res[0][3] == res[1][3] and res[0][1] != res[1][1]:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        result_x=[]\n",
    "        result_y=[]\n",
    "        def dsf(node,father,deep):\n",
    "            nonlocal result_x\n",
    "            nonlocal result_y\n",
    "            if not node:\n",
    "                return \n",
    "            if node.val==x:\n",
    "                result_x=[father,deep]\n",
    "                \n",
    "            elif  node.val==y:\n",
    "                result_y=[father,deep]\n",
    "               \n",
    "            dsf(node.left,node,deep+1)\n",
    "            dsf(node.right,node,deep+1)\n",
    "        dsf(root,root,0)\n",
    "        if result_x[0]!=result_y[0] and result_x[1]==result_y[1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_parent,x_depth,x_found = None, None, False\n",
    "        y_parent,y_depth,y_found = None, None, False\n",
    "        def dfs(node, depth, parent):\n",
    "            nonlocal y_parent,y_found,y_depth,x_depth,x_found,x_parent\n",
    "            if node is None:\n",
    "               return\n",
    "            if node.val == x:\n",
    "                x_found = True\n",
    "                x_parent = parent\n",
    "                x_depth = depth\n",
    "            elif node.val == y:\n",
    "                y_found = True\n",
    "                y_depth = depth\n",
    "                y_parent = parent\n",
    "            if x_found and y_found:\n",
    "                return\n",
    "            dfs(node.right,depth+1, node)\n",
    "            if x_found and y_found:\n",
    "                return\n",
    "            dfs(node.left,depth+1, node)\n",
    "            if x_found and y_found:\n",
    "                return\n",
    "        dfs(root, 0, None)\n",
    "        return x_depth == y_depth and x_parent != y_parent\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        parent={root.val:0} \n",
    "        level={root.val:0}    \n",
    "        depth=0\n",
    "        def ds(root,parent,depth,x,y):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val==x:\n",
    "                level[x]=depth+1\n",
    "            if root.val==y:\n",
    "                level[y]=depth+1\n",
    "            if root.left:                \n",
    "                parent[root.left.val]=root.val\n",
    "                ds(root.left,parent,depth+1,x,y)                \n",
    "            if root.right:\n",
    "                parent[root.right.val]=root.val\n",
    "                ds(root.right,parent,depth+1,x,y)                \n",
    "\n",
    "        ds(root,parent,depth,x,y)\n",
    "\n",
    "        print('parent:',parent)\n",
    "        print('level:',level)\n",
    "   \n",
    "        if level[x]==level[y] and parent[x]!=parent[y]:\n",
    "            return True\n",
    "        else:\n",
    "            return False      \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        q = [root]\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            level = []\n",
    "            for _ in range(n):\n",
    "                node = q.pop(0)\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                if node.left and node.right:\n",
    "                    if (node.left.val == x and node.right.val == y) or (node.left.val == y and node.right.val == x):\n",
    "                        return False\n",
    "                    \n",
    "            if (x in level) and (y in level):\n",
    "                return True\n",
    "            elif (x in level) and (y not in level):\n",
    "                return False\n",
    "            elif (x not in level) and (y in level):\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            cur_layer = []\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                node = queue.pop(0)\n",
    "                if node:\n",
    "                    cur_layer.append(node.val)\n",
    "                    queue.append(node.left)\n",
    "                    queue.append(node.right)\n",
    "                else:\n",
    "                    cur_layer.append(0)\n",
    "        \n",
    "            if x in cur_layer and y in cur_layer:\n",
    "                index1 = cur_layer.index(x)\n",
    "                index2 = cur_layer.index(y)\n",
    "                if index1 > index2:\n",
    "                   index1,index2 = index2,index1\n",
    "                if index1 + 1 == index2 and index1 % 2 == 0:\n",
    "                    return False \n",
    "                return True \n",
    "            if x in cur_layer or y in cur_layer:\n",
    "                return False \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        # 策略是搜索x的深度和父亲  同理也找到y的深度和父亲\n",
    "        def search(rt,tar,depth,father) :\n",
    "            if rt.val == tar :\n",
    "                return depth , father\n",
    "            if rt.left :\n",
    "                d , f = search(rt.left , tar , depth + 1 , rt) \n",
    "                if d != -1 and f != -1 :\n",
    "                    return d , f \n",
    "            if rt.right :\n",
    "                d , f = search(rt.right , tar , depth + 1 , rt) \n",
    "                if d != -1 and f != -1 :\n",
    "                    return d , f \n",
    "            return -1,-1\n",
    "        depthx , fatherx = search(root,x,0,-1)\n",
    "        depthy , fathery = search(root,y,0,-1)\n",
    "        return depthx == depthy and fatherx != fathery "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_node, x_parent, x_depth = None, None, None\n",
    "        y_node, y_parent, y_depth = None, None, None\n",
    "\n",
    "        def traverse(node, parent, depth):\n",
    "            nonlocal x_node, x_parent, x_depth, y_node, y_parent, y_depth\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            if node.val == x:\n",
    "                x_node, x_parent, x_depth = node, parent, depth\n",
    "            if node.val == y:\n",
    "                y_node, y_parent, y_depth = node, parent, depth\n",
    "            \n",
    "            if x_node and y_node:\n",
    "                return\n",
    "            traverse(node.left, node, depth + 1)\n",
    "            if x_node and y_node:\n",
    "                return\n",
    "            traverse(node.right, node, depth + 1)\n",
    "\n",
    "        traverse(root, None, 1)\n",
    "\n",
    "        return x_depth == y_depth and x_parent != y_parent\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        res = []\n",
    "        def digui(root, depth):\n",
    "            if len(res) == 2:\n",
    "                return\n",
    "            elif root == None:\n",
    "                return\n",
    "            else:\n",
    "                temp = []\n",
    "                if root.left != None:\n",
    "                    if root.left.val == x or root.left.val == y:\n",
    "                        temp.append(root.left.val)\n",
    "                if root.right != None:\n",
    "                    if root.right.val == x or root.right.val == y:\n",
    "                        temp.append(root.right.val)\n",
    "                if temp != []:\n",
    "                    temp.append(depth + 1)\n",
    "                    res.append(temp)\n",
    "                digui(root.left, depth + 1)\n",
    "                digui(root.right, depth + 1)\n",
    "        \n",
    "        digui(root, 0)\n",
    "        if len(res) == 2 and res[0][1] == res[1][1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        def fun(root,pre,depth,x,y):\n",
    "            if not root:return \n",
    "            if root.val == x:\n",
    "                    self.a = [pre,depth]\n",
    "            elif root.val == y:\n",
    "                    self.b = [pre,depth]\n",
    "            else:\n",
    "                fun(root.left,root,depth+1,x,y)\n",
    "                fun(root.right,root,depth+1,x,y)\n",
    "\n",
    "        self.a,self.b = [0,0],[0,0]\n",
    "        fun(root,0,0,x,y)\n",
    "        return self.a[0] != self.b[0] and self.a[1] == self.b[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        # 深度相同（同一层）但父节点不同的两个结点被称为堂兄弟结点\n",
    "        queue = deque([root, ])  # 初始化队列为根节点\n",
    "        flag = False\n",
    "        while queue:\n",
    "            size = len(queue)  # size是当前层结点个数\n",
    "            level = []  # 临时数组，记录当前层结点值\n",
    "\n",
    "            for _ in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if not cur:  # 在队列添加cur左右子节点的时候，可能会遇到cur左右子节点为空的情况，此时直接跳出就好了\n",
    "                    level.append(None)\n",
    "                    continue\n",
    "                level.append(cur.val)\n",
    "                queue.append(cur.left)\n",
    "                queue.append(cur.right)\n",
    "\n",
    "            # 深度相同（同一层）但父节点不同的两个结点被称为堂兄弟结点\n",
    "            if x in level and y in level:  # 前提条件：同一层\n",
    "                # 给定值x，y的索引差\n",
    "                index_diff = abs(level.index(x) - level.index(y))  \n",
    "                # level的二维数组表现形式，其中一维数组表示左孩子和右孩子结点值\n",
    "                two_dimen = [level[i:i+2] for i in range(0, len(level), 2)]  \n",
    "                # 由于二叉树的层序遍历并不是有序递增的，所以需要设置两个目标数组\n",
    "                a = [x, y]  # 目标数组\n",
    "\n",
    "                # 如果两目标结点x，y索引差大于等于2则二者一定是堂兄弟结点,或者他们相邻且相邻结点值并不为左右孩子结点值\n",
    "                if index_diff >= 2 or index_diff==1 and a not in two_dimen and a[::-1] not in two_dimen:\n",
    "                    flag = True\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_father, x_depth = None, None\n",
    "        y_father, y_depth = None, None\n",
    "        deque,depth = collections.deque(), 0\n",
    "        deque.append([root, None])\n",
    "        while deque:\n",
    "            depth +=1 \n",
    "            for _ in range(len(deque)):\n",
    "                node, node_father = deque.popleft()\n",
    "                if node.val == x:\n",
    "                    x_father = node_father\n",
    "                    x_depth = depth\n",
    "                if node.val == y:\n",
    "                    y_father = node_father\n",
    "                    y_depth = depth\n",
    "                if node.left: \n",
    "                    deque.append([node.left, node.val])\n",
    "                if node.right: \n",
    "                    deque.append([node.right, node.val])\n",
    "        return x_father != y_father and x_depth == y_depth\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        self.dx = self.dy = -1\n",
    "        self.cousins = True\n",
    "        def helper(node, d):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if node.val == x:\n",
    "                self.dx = d\n",
    "            \n",
    "            if node.val == y:\n",
    "                self.dy = d\n",
    "\n",
    "            if node.left and node.right and ((node.left.val == x and node.right.val == y) or (node.left.val == y and node.right.val == x)):\n",
    "                self.cousins = False\n",
    "\n",
    "            helper(node.left, d+1)\n",
    "            helper(node.right, d+1)\n",
    "\n",
    "        helper(root, 0)\n",
    "\n",
    "        return self.cousins and self.dx != -1 and self.dx == self.dy\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        deep = [0] * 101 \n",
    "        fa = [-1] * 101 \n",
    "        def dfs(u, d, pre):\n",
    "            if u is None:\n",
    "                return \n",
    "            deep[u.val] = d \n",
    "            fa[u.val] = pre\n",
    "            if u.left:\n",
    "                dfs(u.left, d+1, u.val) \n",
    "            if u.right:\n",
    "                dfs(u.right, d+1, u.val)\n",
    "        dfs(root, 0, -1)\n",
    "        if deep[x] == deep[y] and fa[x]!=fa[y]:\n",
    "            return True \n",
    "        else:\n",
    "            return False  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:  \n",
    "        def dg(root,pre,depth):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.val == x:\n",
    "                self.a = [pre,depth]\n",
    "            elif root.val == y:\n",
    "                self.b = [pre,depth]\n",
    "            else:\n",
    "                dg(root.left,root,depth+1)\n",
    "                dg(root.right,root,depth+1)\n",
    "        self.a, self.b = [0,0], [0,0]\n",
    "        dg(root,0,0)\n",
    "        return self.a[0] != self.b[0] and self.a[1] == self.b[1]\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_parent, x_depth, x_found = None, None, False\n",
    "        y_parent, y_depth, y_found = None, None, False\n",
    "\n",
    "        def dfs(node, depth, parent):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found\n",
    "            if node.val == x:\n",
    "                x_parent, x_depth, x_found = parent, depth, True\n",
    "            elif node.val == y:\n",
    "                y_parent, y_depth, y_found = parent, depth, True\n",
    "            \n",
    "            if x_found and y_found:\n",
    "                return\n",
    "            \n",
    "            dfs(node.left, depth+1, node)\n",
    "            dfs(node.right, depth+1, node)\n",
    "        \n",
    "        dfs(root, 0, None)\n",
    "        return x_depth == y_depth and x_parent != y_parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        q = deque([(root, 0, -1)]) # root, depth, parent\n",
    "        d = defaultdict(list)\n",
    "        while q:\n",
    "            node, depth, parent = q.popleft()\n",
    "            d[node.val].extend([depth, parent])\n",
    "            if node.left:\n",
    "                q.append((node.left, depth + 1, node))\n",
    "            if node.right:\n",
    "                q.append((node.right, depth + 1, node))\n",
    "        return d[x][0] == d[y][0] and d[x][1] != d[y][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # BFS. Time O(n) Space O(n)\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        if not root: return []\n",
    "        queue = deque([(root, None)])\n",
    "        res = []\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            xParents, yParents = set(), set()\n",
    "            for _ in range(n):\n",
    "                node, parent = queue.popleft()\n",
    "                if node.val == x: xParents.add(parent)\n",
    "                if node.val == y: yParents.add(parent)\n",
    "                if node.left:\n",
    "                    queue.append((node.left, node))\n",
    "                if node.right:\n",
    "                    queue.append((node.right, node))\n",
    "            for xParent in xParents:\n",
    "                for yParent in yParents:\n",
    "                    if xParent != yParent:\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        depth = {}\n",
    "        father = {}\n",
    "        def dfs( root , parent):\n",
    "            if not root :\n",
    "                return\n",
    "            depth[root.val] = depth[parent.val] + 1 if parent else 0 \n",
    "            father[root.val] = parent\n",
    "            dfs(root.left , root)\n",
    "            dfs(root.right, root)\n",
    "        dfs(root, None)\n",
    "        return depth[x] == depth[y] and father[x] != father[y]\n",
    "\n",
    "        # if not root:\n",
    "        #     return False\n",
    "        # queue = [root]\n",
    "        # while queue:\n",
    "        #     cur_layer = []\n",
    "        #     size = len(queue)\n",
    "        #     # 循环开始时，队列中的元素个数就是当前层结点的个数\n",
    "        #     for _ in range(size):\n",
    "        #         node = queue.pop(0)\n",
    "        #     # 把一层的结点值都放进来，如果遇到空结点，放置 0，\n",
    "        #     # 题目中说\"每个节点的值都是唯一的、范围为 1 到 100 的整数。\"\n",
    "        #     # 所以，你放 101 都是可以的\n",
    "        #         if node:\n",
    "        #             cur_layer.append(node.val)\n",
    "        #             queue.append(node.left)\n",
    "        #             queue.append(node.right)\n",
    "        #         else:\n",
    "        #             cur_layer.append(0)\n",
    "        \n",
    "        #     if x in cur_layer and y in cur_layer:\n",
    "        #         index1 = cur_layer.index(x)\n",
    "        #         index2 = cur_layer.index(y)\n",
    "        #         if index1 > index2:\n",
    "        #            index1,index2 = index2,index1\n",
    "        #         if index1 + 1 == index2 and index1 % 2 == 0:\n",
    "        #     # 如果这两个索引都在一层，只有一种情况需要排除\n",
    "        #     # 那就是两个结点挨着，并且索引小的结点的索引序号是偶数\n",
    "        #             return False \n",
    "        #         return True \n",
    "        #     if x in cur_layer or y in cur_layer:\n",
    "        #         return False \n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        # 深度相同（同一层）但父节点不同的两个结点被称为堂兄弟结点\n",
    "        queue = deque([root, ])  # 初始化队列为根节点\n",
    "        flag = False\n",
    "        while queue:\n",
    "            size = len(queue)  # size是当前层结点个数\n",
    "            level = []  # 临时数组，记录当前层结点值\n",
    "\n",
    "            for _ in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if not cur:  # 在队列添加cur左右子节点的时候，可能会遇到cur左右子节点为空的情况，此时直接跳出就好了\n",
    "                    level.append(None)\n",
    "                    continue\n",
    "                level.append(cur.val)\n",
    "                queue.append(cur.left)\n",
    "                queue.append(cur.right)\n",
    "\n",
    "            # 深度相同（同一层）但父节点不同的两个结点被称为堂兄弟结点\n",
    "            if x in level and y in level:  # 前提条件：同一层\n",
    "                # 给定值x，y的索引差\n",
    "                index_diff = abs(level.index(x) - level.index(y))  \n",
    "                # level的二维数组表现形式，其中一维数组表示左孩子和右孩子结点值\n",
    "                two_dimen = [level[i:i+2] for i in range(0, len(level), 2)]  \n",
    "                # 由于二叉树的层序遍历并不是有序递增的，所以需要设置两个目标数组\n",
    "                a = [x, y]  # 目标数组\n",
    "                b = a[::-1]  # 目标数组\n",
    "\n",
    "                # 如果两目标结点x，y索引差大于等于2则二者一定是堂兄弟结点,或者他们相邻且相邻结点值并不为左右孩子结点值\n",
    "                if index_diff >= 2 or index_diff==1 and a not in two_dimen and b not in two_dimen:\n",
    "                    flag = True\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        # self.tem1 = self.tem2 = [[-1,-2]]\n",
    "        if not root:\n",
    "                return False\n",
    "        if not root.left or not root.right:\n",
    "                return False\n",
    "        x_h = y_h = x_p = y_p = None\n",
    "\n",
    "        queue = [(root,None)]\n",
    "        height = 0\n",
    "        flag = 0\n",
    "        while queue:\n",
    "            num = len(queue)\n",
    "            height += 1\n",
    "            for i in range(num):\n",
    "                cur, parent = queue.pop(0)\n",
    "\n",
    "                if cur.val == x:\n",
    "                    x_h = height\n",
    "                    x_p = parent\n",
    "                    flag += 1\n",
    "                if cur.val == y:\n",
    "                    y_h = height\n",
    "                    y_p = parent\n",
    "                    flag += 1\n",
    "\n",
    "                if flag == 2:\n",
    "                    # break\n",
    "                    return x_h == y_h and x_p != y_p\n",
    "\n",
    "                \n",
    "                if cur.left:\n",
    "                    queue.append((cur.left,cur))\n",
    "                if cur.right:\n",
    "                    queue.append((cur.right,cur))\n",
    "\n",
    "        return x_h == y_h and x_p != y_p\n",
    "                \n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        parent={root.val:0} \n",
    "        level={root.val:0}    \n",
    "        depth=0\n",
    "        def ds(root,parent,depth,x,y):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val==x:\n",
    "                level[x]=depth+1\n",
    "            if root.val==y:\n",
    "                level[y]=depth+1\n",
    "            if root.left:                \n",
    "                parent[root.left.val]=root.val\n",
    "                ds(root.left,parent,depth+1,x,y)                \n",
    "            if root.right:\n",
    "                parent[root.right.val]=root.val\n",
    "                ds(root.right,parent,depth+1,x,y)                \n",
    "\n",
    "        ds(root,parent,depth,x,y)\n",
    "\n",
    "        print('parent:',parent)\n",
    "        print('level:',level)\n",
    "   \n",
    "        if level[x]==level[y] and parent[x]!=parent[y]:\n",
    "            return True\n",
    "        else:\n",
    "            return False      \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        result_x = []\n",
    "        result_y = []\n",
    "        def dfs(node,parent,deep):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal result_x, result_y\n",
    "            if node.val == x:\n",
    "                result_x = [parent,deep]\n",
    "            elif node.val == y:\n",
    "                result_y = [parent,deep]\n",
    "            dfs(node.left,node,deep + 1)\n",
    "            dfs(node.right,node,deep + 1)\n",
    "        dfs(root,root,0)\n",
    "        return result_x[0] != result_y[0] and result_x[1] == result_y[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        if not root:    return None\n",
    "        def dfs(pre, root, target, depth):\n",
    "            if not root:    return 0\n",
    "\n",
    "            if root.val == target:\n",
    "                return depth, pre\n",
    "            return dfs(root, root.left, target, depth+1) or dfs(root, root.right, target, depth+1)\n",
    "\n",
    "        d1, parent1 = dfs(None, root, x, 0)\n",
    "        d2, parent2 = dfs(None, root, y, 0)\n",
    "        return d1 == d2 and parent1 != parent2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            counter = 0\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node.left and node.right and ((node.left.val == x and node.right.val == y) or (node.left.val == y and node.right.val == x)):\n",
    "                    return False\n",
    "                if node.val == x or node.val == y:\n",
    "                    counter += 1\n",
    "                    if counter == 2:\n",
    "                        return True\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        ans=defaultdict(list)\n",
    "        def dfs(node,depth,parent):\n",
    "            if not node:\n",
    "                return\n",
    "            ans[node.val]=[depth,parent]\n",
    "            dfs(node.left,depth+1,node.val)\n",
    "            dfs(node.right,depth+1,node.val)\n",
    "        dfs(root,1,0)\n",
    "        return ans[x][0]==ans[y][0] and ans[x][1]!=ans[y][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "\n",
    "        x_p = None\n",
    "        x_height = 0\n",
    "\n",
    "        y_p = None\n",
    "        y_height = 0\n",
    "        \n",
    "        def traversal(root, v, p, h):\n",
    "            if not root:\n",
    "                # return None\n",
    "                return p,h\n",
    "            if (root.left and root.left.val == v) or (root.right and root.right.val == v):\n",
    "                p = root.val\n",
    "                return p,h\n",
    "            h +=1\n",
    "            # return traversal(root.left,v,p,h) or traversal(root.right,v,p,h)\n",
    "            # return traversal(root.left,v,p,h) if traversal(root.left,v,p,h) else traversal(root.right,v,p,h)\n",
    "            left = traversal(root.left,v,p,h)\n",
    "            right = traversal(root.right,v,p,h)\n",
    "            return left if left[0] else right\n",
    "            # return left if left else right\n",
    "\n",
    "        x_p, x_height = traversal(root, x, x_p, x_height)\n",
    "        print('x_p, x_height',x_p, x_height)\n",
    "        y_p, y_height = traversal(root, y, y_p, y_height)\n",
    "\n",
    "        print('x_p, x_height',x_p, x_height)\n",
    "        print('y_p, y_height',y_p, y_height)\n",
    "        if (x_p != y_p) and (x_p != None) and (y_p !=None) and x_height == y_height:\n",
    "            return True\n",
    "        else: return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        x_depth, x_father = None, None\n",
    "        y_depth, y_father = None, None\n",
    "        def dfs(root: TreeNode, father: TreeNode, depth: int):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.val == x:\n",
    "                nonlocal x_depth, x_father\n",
    "                x_depth, x_father = depth, father\n",
    "            if root.val == y:\n",
    "                nonlocal y_depth, y_father\n",
    "                y_depth, y_father = depth, father\n",
    "            if x_father and y_father:\n",
    "                return\n",
    "            dfs(root.left, root, depth + 1)\n",
    "            if x_father and y_father:\n",
    "                return\n",
    "            dfs(root.right, root, depth + 1)\n",
    "        \n",
    "        dfs(root, None, 0)\n",
    "\n",
    "        return False if x_depth != y_depth or x_father == y_father else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None, parent=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        from collections import deque\n",
    "        dq = deque()\n",
    "        dq.appendleft((root, None))\n",
    "        level_parents = []\n",
    "        while dq:\n",
    "            for i in range(len(dq)):\n",
    "                cur_node, parent = dq.popleft()\n",
    "                if cur_node.val == x or cur_node.val == y:\n",
    "                    level_parents.append(parent)\n",
    "                if cur_node.left:\n",
    "                    dq.append((cur_node.left, cur_node))\n",
    "                if cur_node.right:\n",
    "                    dq.append((cur_node.right, cur_node))\n",
    "            if not level_parents:\n",
    "                continue\n",
    "            if len(level_parents) == 1:\n",
    "                return False\n",
    "            if len(level_parents) == 2:\n",
    "                return level_parents[0] != level_parents[1]\n",
    "        # return False\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "    # def get_parent(self, root):\n",
    "    #     #DFS建立父节点\n",
    "    #     if not root.left and not root.right:\n",
    "    #         return\n",
    "    #     while root.left:\n",
    "    #         root.left.parent = root\n",
    "    #         root = root.left\n",
    "    #     while root.right:\n",
    "    #         root.right.parent = root\n",
    "    #         root = root.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        parent = dict()\n",
    "        parent[root.val] = [-1, 0]\n",
    "\n",
    "        def dfs(root, level):\n",
    "            if root.left:\n",
    "                parent[root.left.val] = [root.val, level+1]\n",
    "                dfs(root.left, level+1)\n",
    "\n",
    "            if root.right:\n",
    "                parent[root.right.val] = [root.val, level+1]\n",
    "                dfs(root.right, level+1)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return parent[x][1] == parent[y][1] and parent[x][0] != parent[y][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        # 先写一个标准的parent、dept的dfs\n",
    "        x_p = None\n",
    "        y_p = None\n",
    "        x_d = 0\n",
    "        y_d = 0\n",
    "        def dfs(node, parent, dept):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal x_p, y_p, x_d, y_d\n",
    "            if node.val == x:\n",
    "                x_p = parent\n",
    "                x_d = dept\n",
    "            elif node.val == y:\n",
    "                y_p = parent\n",
    "                y_d = dept\n",
    "            dfs(node.left, node, dept+1)\n",
    "            dfs(node.right, node, dept+1)\n",
    "        dfs(root, root, 0)\n",
    "        return x_p != y_p and x_d == y_d\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:\n",
    "        father = {root.val:None}\n",
    "        d = {}\n",
    "        q = [(root, 0)]\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                node, depth = q.pop(0)\n",
    "                d[node.val] = depth\n",
    "                if node.left:\n",
    "                    father[node.left.val] = node.val\n",
    "                    q.append((node.left, depth + 1))\n",
    "                if node.right:\n",
    "                    father[node.right.val] = node.val\n",
    "                    q.append((node.right, depth + 1))\n",
    "        print(father)\n",
    "        print(d)\n",
    "        return father[x] != father[y] and d[x] == d[y]\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
